Logic

An open sentence is a boolean expression that contains unbound variables. The truth of an open sentence cannot be evaluated until specific values are substituted for the unbound variables. If a set of values makes an open sentence true when substituted for the unbound variables, the values are said to satisfy the sentence. Typically, a universe of discourse is defined, from which the values can be chosen.

Here are some example open sentences:

1. `S sube ZZ` (`S` is unbound)
2. `y^2-5y+6=0` (`y` is unbound)

A logical implication is a statement that relates two propositions. If `P` and `Q` and `P` implies `Q`, then `P` is called the hypothesis (or antecedant) and `Q` is called the conclusion (or consequent). The implication can be written as `P => Q`, `P |== Q`, or `P :. Q` (in decreasing order of popularity), all of which can be read "`P` implies `Q`" or "`P` entails `Q`". A logical implication is false only if the hypothesis is true but the conclusion is false.

When the sentence "if A, then B" is encountered, where `A` or `B` is an open sentence, it is generally interpreted as a universally quantified implication: `(AA x in UU)(A => B)`.

The symbol `AA` (read "for all" or "for every") is called the universal quantifier. It is generally followed by a variable name, a set or expression restricting that variable, and open sentence about that variable. This forms a new sentence which asserts that all possible substitutions for the variable satisfy the open sentence. If the set is omitted, it is assumed to be `UU`.

For instance, the sentence `A sube B` can be defined using the universal quantifier: `(AA x in A)(x in B)`. This says that every element in `A` exists in `B`, which is exactly what `A sube B` means. The parentheses in the sentence are not strictly required. `AA x in A (x in B)` means the same thing, as does `AA x in A` `x in B`. Note that the sentence containing the universal quantifier may be false. For example: `(AA n in NN)(n < 0)`. This asserts that all natural numbers are negative, but the assertion is false.

The symbol `EE` (read "there exists") is called the existential quantifier. It is generally followed by a variable name, a set or expression restricting that variable, and open sentence about that variable. This forms a new sentence which asserts that there exists at least one substition for the variable that satisfies the open sentence. If the set is omitted, it is assumed to be `UU`.

For instance, the sentence `a div b` can be defined using the existential quantifier: `(EE t in ZZ)(at=b)`. This says that there exists an integer `t` such that `at=b`. The parentheses in the sentence are not strictly required. `EE t in ZZ (at=b)` means the same thing, as does `EE t in ZZ` `at=b`. Note that the sentence containing the existential quantifier may be false. For example: `(EE n in NN)(n < 0)`. This asserts that there exists at least one natural number that is negative, but the assertion is false.

A truth set of an open sentence is the complete set of values that, when substituted for the open variables in the sentence, make it true. For example, the truth set of `x^2-4x-5=0` (`UU=RR`) is {-1,5}.

A counterexample is a set of values that, when substituted into a logical implication, makes the hypothesis of the implication true and the conclusion false.

A vacuously true statement is a logical implication that is true, but the truth set of its hypothesis is the empty set. An example of a vacuously true statement is: "If `x` is a real number with `x^2<0`, then `x=17`." The statement is true because there does not exist a counterexample, but it's rather useless because there is no situation to which this statement can be applied.